package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/flip-binary-tree-to-match-preorder-traversal/
 * @create 2025/9/25 19:07
 * @since JDK17
 */

public class Solution60 {
    List<Integer> ans = new ArrayList<>();
    int[] d;
    int n;
    boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.val != d[n]) {
            return false;
        }
        int t = ++n;    // 不用翻转
        boolean p1 = dfs(root.left) && dfs(root.right);
        if (p1 == false) {  // 要翻转
            ans.add(root.val);
            p1 = dfs(root.right) && dfs(root.left);
        }
        return p1;
    }
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        d = voyage;
        if (dfs(root)) {
            return ans;
        } else {
            return List.of(-1);
        }
    }
}
